package 排序;

class ListNode {
  int val;
  ListNode next;
  ListNode() {}
  ListNode(int val) { this.val = val; }
  ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Sort {
    public void insertSort(int[] array) {
        for(int i = 1; i < array.length; i++) {
            int key = array[i];
            int j = i - 1;
            for(; j >= 0; j--) {
                if(array[j] > key) {
                    array[j + 1] = array[j];
                }else {
                    break;
                }
            }
            array[j + 1] = key;
        }
    }
    public ListNode insertionSortList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode headNode = new ListNode(Integer.MIN_VALUE, head);
        ListNode curNext = head.next;
        while(curNext != null) {
            ListNode prev = headNode;
            ListNode cur = headNode.next;
            while(cur != curNext) {
                if(cur.val > curNext.val) {
                    cur.next = curNext.next;
                    curNext.next = cur;
                    prev.next = curNext;
                }
                prev = cur;
                cur = cur.next;
            }
            curNext = curNext.next;
        }
        return headNode.next;
    }
}
